The present invention relates to flow control in a communications network and, more particularly, to an Explicit Rate (ER) computation for Available Bit Rate (ABR) traffic to achieve flow control in an Asynchronous Transfer Mode (ATM) network.
The ATM Forum Traffic Management Specification, Version 4.0, 1996 (TM4.0), specifies five classes of service to support the diverse requirements of multimedia traffic: Constant Bit Rate (CBR), Real-Time Variable Bit Rate (rt-VBR), Non-Real-Time Variable Bit Rate (nrt-VBR), Available Bit Rate (ABR), and Unspecified Bit Rate (UBR). The UBR traffic class provides a best-effort service: No amount of bandwidth is guaranteed, and any cells may be discarded. ABR and UBR are best suited for LAN internetworking and other types of data traffic. UBR is directed at delay-tolerant applications (e.g., file transfer and e-mail). It provides no feedback about network congestion to the user or application. Thus, UBR increases the risk of discarded cells, which in turn increases network traffic because of the lost cells that must be retransmitted.
The ATM Forum defined ABR service to improve service to bursty sources that would instead use UBR. ABR is intended for data applications that can adapt to time-varying bandwidth and tolerate unpredictable end-to-end cell delays. ABR connections share the available bandwidth. The concept of available bandwidth is intrinsic to the service; it is whatever bandwidth exists in excess of CBR/VBR traffic, as defined by the network provider. Thus, the ABR traffic is allowed to use bandwidth that would otherwise be unused, increasing the link utilization without affecting the quality of service (QoS) of CBR/VBR connections. The main practical difference between ABR and UBR is that for ABR, the network provides congestion information to the application. This lets the application constantly modify the transmission rate, achieving the best throughput.
The ABR service class is designed so that applications can grab any unused network resources that VBR and CBR traffic does not utilize, i.e., unused bandwidth and buffer space. Gains due to statistical resource utilization, however, come at the risk of potential congestion when many applications compete for network resources. Therefore, proper congestion control must be in place to ensure that network resources can be shared in a fair manner and that performance objectives such as cell loss ratio can be maintained. In TM4.0, the ATM Forum has specified a flow control mechanism which supports several types of feedback to control the source rate in response to changing transfer characteristics. The purpose of feedback in the context of ABR service is to use available bandwidth (after allocation to CBR and VBR sources) efficiently and allocate it evenly among active ABR connections. Other objectives include instantaneous access to bandwidth which is required to offer dynamic ABR service. This feedback information is conveyed to the source, which adapts its traffic in accordance with the feedback. The feedback information includes the state of congestion and a fair share of the available bandwidth according to a network-specific allocation policy. To ensure interoperability, an ABR end system must always implement the standard-defined source and destination behavior in TM4.0.
The ABR congestion control scheme specified in TM4.0 is a rate-based, closed-loop control that utilizes the feedback information from the network to regulate the rate of cell transmission at the source. FIG. 1 illustrates the basic operation of ABR congestion control. In network 100, source 102 transmits data cells 108 to destination 104 via one or more switches in network 100, one of which, switch 106, is shown in FIG. 1. Source 102 also generates special probe cells 110 referred to as forward resource management (RM) cells in proportion to its current data cell rate. The parameter Nrm specifies the maximum number of cells a source may send for each forward RM cell. Thus, source 102 normally sends a forward RM cell 110 for every Nrm-1 data cells 108. Destination 104 turns around and sends RM cells 110 back to source 102 in the other direction. These cells are referred to as backward RM cells, and are shown as cells 112 in FIG. 1.
The RM cells, which can be examined and modified by the switches in both forward and backward directions, carry feedback information of the state of congestion and the fair rate allocation. TM4.0, which is incorporated herein by reference, presents a precise definition of the source end system and destination end system behavior, the content and format of RM cells, and a range of feasible switch mechanisms. These mechanisms are characterized by different levels of complexity and achieve varying degrees of fairness. The wide range of options demonstrates the flexibility in the choice of switch mechanisms available with the rate-based framework. With reference to FIG. 1, the following summarizes the operation of the rate-based control scheme, the details of which are found in TM4.0.
A switch shall implement at least one of the following methods to control congestion:
a) Explicit Forward Congestion Indication (EFCI) marking: Switch 106 may set the EFCI condition in the header of an ATM data cell 108 (using the payload type field) as it passes in the forward direction. This causes destination end system 104 to set the congestion indication (CI) bit in a backward RM (BRM) cell 112. Most first-generation ATM switches implemented this mechanism before the RM cell was fully defined.
b) Relative rate marking: Switch 106 may set the CI or the no increase (NI) bit of a passing forward RM cell 110 or backward RM cell 112. If the bit is set in a forward RM (FRM) cell 110, that bit will remain set in the corresponding BRM cell 112. More rapid results are achieved by setting one of these bits in a passing BRM cell 112. To achieve the most rapid result, a switch may generate a BRM cell 112 with the Cl or NI bit set rather than wait for a passing BRM cell.
c) Explicit rate marking: Switch 106 may reduce the value of the explicit rate (ER) field of an FRM cell 110 and/or BRM cell 112.
Switches that implement the first two options above are known as binary switches; they can reduce implementation complexity but may result in unfairness, congestion oscillation, and slow response. Switches that implement the last option are generally called ER switches and require sophisticated mechanisms at the switches to compute a fair share of the bandwidth. The standard-defined source and destination behaviors, however, allow interoperation of the above three options.
With reference to FIG. 1, source end system 102 sets up a connection with a call setup request for ABR connection. During this signaling setup, values for a set of ABR-specific parameters are signaled by source end system 102 and the network elements. Some of these parameters are requested by source 102, based on its requirements, and can subsequently be modified by the network (e.g., Peak Cell Rate (PCR), Minimum Cell Rate (MCR)), while others can be set by the network (e.g., those impacting rate increase/decrease behavior such as Rate Increase Factor (RIF), Rate Decrease Factor (RDF), and Nrm). An application using ABR service specifies a Peak Cell Rate (PCR) that it will use and a Minimum Cell Rate (MCR) that it requires. The network allocates resources so that all ABR applications receive at least their MCR capacity. The network then shares any unused capacity in a fair and controlled fashion among all ABR sources. Any capacity that ABR sources do not use remains available for UBR traffic.
Once source 102 has received permission, it begins scheduling cells for transmission at the allowed cell rate (ACR). The ACR is initially set to the initial cell rate (ICR) and is always bounded by the MCR and the PCR. Transmission of data cells 108 is preceded by transmission of a forward RM cell 110. Source 102 continues to send forward RM cells 110, typically after every (Nrm-1) data cells 108. Source 102 places the ACR value in the current cell rate (CCR) field of forward RM cell 110, and the rate at which it wishes to transmit cells (usually the PCR value) in the ER field of forward RM cell 110. Forward RM cells 110 traverse forward through the network, and destination 104 turns RM cells 110 around in the backward direction so that they become backward RM cells 112. Intermediate switches on the path notify source 102 of congestion by marking the EFCI bit in data cells 108 and the CI or NI bit of a forward RM cell 110 or backward RM cell 112, and/or reducing the ER value in forward RM cells 110 or backward RM cells 112. Switches capable of only EFCI marking ignore the content of RM cells.
Upon return of backward RM cell 112, source 102 should adapt its ACR to the information carried in the RM cell. Feedback from the network appears periodically as a sequence of backward RM cells 112. If CI is not set, source 102 may linearly increase its ACR by a fixed increment (RIF*PCR). This increase can reach the ER value in backward RM cell 112, but should never exceed the PCR. If CI is set, source 102 must exponentially decrease its ACR by an amount greater than or equal to a proportion of its current ACR, (RDF*ACR). The factors RIF and RDF control the rate at which the source increases and decreases its rate, respectively. If the ACR is still greater than the returned ER, source 102 must further decrease its ACR to the returned ER value, although it should never be below the MCR. If NI is set, source 102 should observe the CI and ER fields in the RM cell, but it is not allowed to increase the ACR above its current value. To make the ABR framework robust to synchronized surges in traffic from different users and to network failures, source 102 also decreases its ACR if it is not taking full advantage of the rate or receiving the expected return flow of RM cells 112.
When forward RM cell 110 arrives at destination 104, destination 104 changes the direction (DIR) bit in the cell and returns it to source 102. If destination 104 is congested and cannot support the rate in the ER field, destination 104 reduces the ER to whatever rate it can support. When returning an RM cell, if destination 104 observes that the EFCI bit is set in the last received data cell 108, it sets the CI bit in a backward RM cell 112 to indicate congestion. If destination 104 experiences congestion, it may also set the CI or NI bit when converting an FRM cell to a BRM cell.
The first generation of ATM switches to support ABR used the EFCI, NI, and CI bits, providing a simple relative-rate control mechanism based on binary feedback information. The inherent shortcomings of the binary approach have recently led to the consideration and implementation of a second generation of ABR service, which uses sophisticated fair rate allocation algorithms that compute fair rates for each connection and convey this information to the sources as an explicit rate. Under this newer approach, a network switch is responsible for allocating the fair share of the bandwidth among all connections that compete at this switch point. Since this allocation policy is implementation-specific, it has been at the center of switch design and implementation. This issue has become an important differentiating factor for the next generation of commercially available switches.
A number of ABR rate control algorithms have been proposed. Kawahara, R., H. Saito, and M. Kawarasaki, xe2x80x9cCharacteristics of ABR Explicit Rate Control Algorithms in WAN Environments and an ABR Control Algorithm Suitable for Public Networks,xe2x80x9d Int""l. Journal of Comm. Systems, vol. 11, 1998, pp. 189-209, and Arulambalam, A., X. Chen and N. Ansari, xe2x80x9cAllocating Fair Rates for Available Bit Rate Service in ATM Networks,xe2x80x9d IEEE Comm. Mag., November 1996, pp. 92-100, summarize existing and proposed fair rate allocation schemes and present their relative merits and detailed performance characteristics. Most existing and proposed rate control schemes are not entirely satisfactory for implementation in public Wide Area Networks (WANs), which have long round-trip times and a great number of multiplexed connections. It is generally very difficult for a rate control scheme to be efficient, fair, and practical to implement at the same time. The effectiveness of any feedback control scheme is limited by the latency of the feedback loop. In particular, when connections traverse several intermediate nodes, extreme unfairness can result. Connections whose feedback delays are smaller and thus have up-to-date rate information can have an unfair advantage over connections that have larger feedback delays. In a WAN, the latency of the feedback loop, coupled with the fact that the amount of buffer space at each node can be less than the bandwidth delay product of the route, can lead to significant degradation in network performance.
A main drawback of most proposed explicit rate control algorithms proposed is that they are based on heuristics and depend on a number of tuning parameters, which must be set correctly, and also on a number of measurements that are costly and difficult to perform. Further, these proposals do not provide any formal design methodology to ensure the stability of the control loop. Two exceptions are the algorithms proposed in Benmohamed, L., and S. M. Meerkov, xe2x80x9cFeedback control of congestion in packet switching networks: The case of a single congested node,xe2x80x9d IEEE/ACM Trans. Networking, vol. 1, no. 6, December 1993, pp. 693-708, and Kolarov, A., and G. Ramamurthy, xe2x80x9cA Control Theoretic Approach to the Design of Closed Loop Rate Based Flow Control for High Speed ATM Networks,xe2x80x9d IEEE INFOCOM""97, Kobe, Japan, April 1997, both of which provide control theoretic methods for the design of closed loop flow control schemes where the issues of stability and fairness are addressed. While these proposed methods are probably stable, they are difficult to implement, especially on a large scale.
It is desirable, therefore, to provide an explicit rate flow control scheme that is simple to implement and is fair to multiple sources. It is more desirable to provide such a scheme that also is scalable with speed, distance, number of users, and number of network nodes. It is even more desirable to provide such a scheme that has provably stable behavior and converges in steady state.
This invention satisfies those desires by providing a simple, stable, scalable method for computing a fair share traffic rate in communication networks.
A method consistent with the present invention controls flow in a network at a network switch that receives data packets and management packets by measuring an aggregate arrival rate of data packets from a plurality of source-destination connections, determining an available capacity on the outgoing link from the switch for data packets based on the maximum capacity of the link, determining a fair share rate for data packets based on the aggregate arrival rate of the data packets, the available capacity of the outgoing link, and a maximum round-trip delay for management packets from source to destination and back to source, and determining a new target rate for the data packets on each of the plurality of connections based on the fair share rate. A method consistent with the present invention further replaces a target rate contained in management packets with the new target rate.
A method consistent with the present invention further measures an aggregate arrival rate of additional data packets of a different type from the data packets and bases the available capacity of the data packets on the aggregate arrival rate of the additional data packets. Further, a method consistent with the present invention determines a fair share rate on the relative weights of the plurality of connections.
Systems are also provided for carrying out the methods consistent with the present invention.
The advantages accruing to the present invention are numerous. Methods and systems consistent with the present invention are easy to implement without requiring a specific switch architecture. They determine an explicit rate allocation that is fair to all sources of ABR traffic. Methods and systems consistent with the present invention are also scalable and exhibit provably stable behavior. They are also robust with respect to system perturbations and bursty sources.
The above desires, other desires, features, and advantages of the present invention will be readily appreciated by one of ordinary skill in the art from the following detailed description of the preferred implementations when taken in connection with the accompanying drawings.